題目

題目大意

給一個 BST，對這棵樹做序列化，並寫一個函數做反序列化。

想法

DFS，自己、左子樹、右子樹，想辦法存 NULL 的情況就知道怎麼停下來了。
優化方式應該是存 binary (? 想說這題蠻水的就直接寫了XD

Code(C++)

// Encodes a tree to a single string.
string serialize(TreeNode* root) {
    if (!root) return ",";
    return to_string(root->val) + "," + serialize(root->left) + serialize(root->right);
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
    auto res = solve(data, 0);
    return res.first;
}

pair<TreeNode*, int> solve(string data, int i) {
    if (data[i] == ',') return {NULL, i};
    string temp = "";
    for(; i < data.size() && data[i] != ','; i++) temp += data[i];
    TreeNode *root = new TreeNode(stoi(temp));
    auto left = solve(data, i+1);
    auto right = solve(data, left.second+1);
    root->left = left.first;
    root->right = right.first;
    return {root, right.second};
}

心得

水水的 tree 題。